

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "traster.h"

/*
#include "img.h"
#include "file.h"
#include "toonz.h"
#include "raster.h"
#include "tmsg.h"
#include "copP.h"*/

/*------------------------------------------------------------------------*/
namespace {
UCHAR First_preseed_table[256] = {
    8, 0, 1, 0, 2, 2, 1, 0, 3, 3, 3, 3, 2, 2, 3, 3, 4, 4, 1, 0, 2, 2, 1, 0,
    4, 4, 3, 3, 2, 2, 3, 3, 5, 5, 1, 5, 2, 2, 1, 5, 5, 5, 5, 5, 2, 2, 5, 5,
    4, 4, 1, 5, 2, 2, 1, 5, 4, 4, 5, 5, 2, 2, 5, 5, 6, 6, 1, 6, 2, 2, 1, 6,
    6, 6, 6, 6, 2, 2, 6, 6, 4, 4, 1, 0, 2, 2, 1, 0, 4, 4, 8, 8, 2, 2, 8, 8,
    6, 6, 1, 6, 2, 2, 1, 6, 6, 6, 6, 6, 2, 2, 6, 6, 4, 4, 1, 0, 2, 2, 1, 0,
    4, 4, 8, 8, 2, 2, 8, 8, 7, 7, 1, 7, 2, 2, 1, 7, 7, 7, 7, 7, 2, 2, 7, 7,
    4, 4, 1, 0, 2, 2, 1, 0, 4, 4, 3, 3, 2, 2, 3, 3, 7, 7, 1, 7, 2, 2, 1, 7,
    7, 7, 7, 7, 2, 2, 7, 7, 4, 4, 1, 5, 2, 2, 1, 5, 4, 4, 5, 5, 2, 2, 5, 5,
    7, 7, 1, 7, 2, 2, 1, 7, 7, 7, 7, 7, 2, 2, 7, 7, 4, 4, 1, 0, 2, 2, 1, 0,
    4, 4, 8, 8, 2, 2, 8, 8, 7, 7, 1, 7, 2, 2, 1, 7, 7, 7, 7, 7, 2, 2, 7, 7,
    4, 4, 1, 0, 2, 2, 1, 0, 4, 4, 8, 8, 2, 2, 8, 8};

static UCHAR Next_point_table[2048] = {
    8, 8, 8, 8, 8, 8, 8, 8, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 2, 2, 2, 2, 2, 2, 2,
    1, 2, 2, 2, 2, 2, 2, 0, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0,
    0, 0, 0, 0, 0, 3, 3, 1, 1, 1, 1, 1, 1, 3, 0, 1, 1, 1, 1, 1, 1, 3, 3, 3, 2,
    2, 2, 2, 2, 3, 0, 0, 2, 2, 2, 2, 2, 3, 3, 1, 2, 2, 2, 2, 2, 3, 0, 1, 2, 2,
    2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 4, 0, 4, 4, 4, 4, 4, 1, 4, 1, 4,
    4, 4, 4, 0, 1, 4, 1, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 0, 0, 4, 2, 4, 4,
    4, 4, 4, 1, 4, 2, 4, 4, 4, 4, 0, 1, 4, 2, 4, 4, 4, 3, 3, 3, 4, 3, 4, 4, 4,
    3, 0, 0, 4, 0, 4, 4, 4, 3, 3, 1, 4, 1, 4, 4, 4, 3, 0, 1, 4, 1, 4, 4, 4, 3,
    3, 3, 4, 2, 4, 4, 4, 3, 0, 0, 4, 2, 4, 4, 4, 3, 3, 1, 4, 2, 4, 4, 4, 3, 0,
    1, 4, 2, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0, 0, 5, 0, 0, 0, 0, 5, 5, 1,
    5, 1, 1, 1, 1, 5, 0, 1, 5, 1, 1, 1, 1, 5, 5, 5, 5, 2, 2, 2, 2, 5, 0, 0, 5,
    2, 2, 2, 2, 5, 5, 1, 5, 2, 2, 2, 2, 5, 0, 1, 5, 2, 2, 2, 2, 3, 3, 3, 5, 3,
    3, 3, 3, 3, 0, 0, 5, 0, 0, 0, 0, 3, 3, 1, 5, 1, 1, 1, 1, 3, 0, 1, 5, 1, 1,
    1, 1, 3, 3, 3, 5, 2, 2, 2, 2, 3, 0, 0, 5, 2, 2, 2, 2, 3, 3, 1, 5, 2, 2, 2,
    2, 3, 0, 1, 5, 2, 2, 2, 2, 5, 5, 5, 5, 5, 4, 4, 4, 5, 0, 0, 5, 0, 4, 4, 4,
    5, 5, 1, 5, 1, 4, 4, 4, 5, 0, 1, 5, 1, 4, 4, 4, 5, 5, 5, 5, 2, 4, 4, 4, 5,
    0, 0, 5, 2, 4, 4, 4, 5, 5, 1, 5, 2, 4, 4, 4, 5, 0, 1, 5, 2, 4, 4, 4, 3, 3,
    3, 5, 3, 4, 4, 4, 3, 0, 0, 5, 0, 4, 4, 4, 3, 3, 1, 5, 1, 4, 4, 4, 3, 0, 1,
    5, 1, 4, 4, 4, 3, 3, 3, 5, 2, 4, 4, 4, 3, 0, 0, 5, 2, 4, 4, 4, 3, 3, 1, 5,
    2, 4, 4, 4, 3, 0, 1, 5, 2, 4, 4, 4, 6, 6, 6, 6, 6, 6, 6, 6, 6, 0, 0, 6, 0,
    6, 0, 0, 6, 6, 1, 6, 1, 6, 1, 1, 6, 0, 1, 6, 1, 6, 1, 1, 6, 6, 6, 6, 2, 6,
    2, 2, 6, 0, 0, 6, 2, 6, 2, 2, 6, 6, 1, 6, 2, 6, 2, 2, 6, 0, 1, 6, 2, 6, 2,
    2, 3, 3, 3, 6, 3, 6, 3, 3, 3, 0, 0, 6, 0, 6, 0, 0, 3, 3, 1, 6, 1, 6, 1, 1,
    3, 0, 1, 6, 1, 6, 1, 1, 3, 3, 3, 6, 2, 6, 2, 2, 3, 0, 0, 6, 2, 6, 2, 2, 3,
    3, 1, 6, 2, 6, 2, 2, 3, 0, 1, 6, 2, 6, 2, 2, 6, 6, 6, 6, 6, 6, 4, 4, 6, 0,
    0, 6, 0, 6, 4, 4, 6, 6, 1, 6, 1, 6, 4, 4, 6, 0, 1, 6, 1, 6, 4, 4, 6, 6, 6,
    6, 2, 6, 4, 4, 6, 0, 0, 6, 2, 6, 4, 4, 6, 6, 1, 6, 2, 6, 4, 4, 6, 0, 1, 6,
    2, 6, 4, 4, 3, 3, 3, 6, 3, 6, 4, 4, 3, 0, 0, 6, 0, 6, 4, 4, 3, 3, 1, 6, 1,
    6, 4, 4, 3, 0, 1, 6, 1, 6, 4, 4, 3, 3, 3, 6, 2, 6, 4, 4, 3, 0, 0, 6, 2, 6,
    4, 4, 3, 3, 1, 6, 2, 6, 4, 4, 3, 0, 1, 6, 2, 6, 4, 4, 5, 5, 5, 5, 5, 6, 5,
    5, 5, 0, 0, 5, 0, 6, 0, 0, 5, 5, 1, 5, 1, 6, 1, 1, 5, 0, 1, 5, 1, 6, 1, 1,
    5, 5, 5, 5, 2, 6, 2, 2, 5, 0, 0, 5, 2, 6, 2, 2, 5, 5, 1, 5, 2, 6, 2, 2, 5,
    0, 1, 5, 2, 6, 2, 2, 3, 3, 3, 5, 3, 6, 3, 3, 3, 0, 0, 5, 0, 6, 0, 0, 3, 3,
    1, 5, 1, 6, 1, 1, 3, 0, 1, 5, 1, 6, 1, 1, 3, 3, 3, 5, 2, 6, 2, 2, 3, 0, 0,
    5, 2, 6, 2, 2, 3, 3, 1, 5, 2, 6, 2, 2, 3, 0, 1, 5, 2, 6, 2, 2, 5, 5, 5, 5,
    5, 6, 4, 4, 5, 0, 0, 5, 0, 6, 4, 4, 5, 5, 1, 5, 1, 6, 4, 4, 5, 0, 1, 5, 1,
    6, 4, 4, 5, 5, 5, 5, 2, 6, 4, 4, 5, 0, 0, 5, 2, 6, 4, 4, 5, 5, 1, 5, 2, 6,
    4, 4, 5, 0, 1, 5, 2, 6, 4, 4, 3, 3, 3, 5, 3, 6, 4, 4, 3, 0, 0, 5, 0, 6, 4,
    4, 3, 3, 1, 5, 1, 6, 4, 4, 3, 0, 1, 5, 1, 6, 4, 4, 3, 3, 3, 5, 2, 6, 4, 4,
    3, 0, 0, 5, 2, 6, 4, 4, 3, 3, 1, 5, 2, 6, 4, 4, 3, 0, 1, 5, 2, 6, 4, 4, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 0, 0, 7, 0, 7, 7, 0, 7, 7, 1, 7, 1, 7, 7, 1, 7, 0,
    1, 7, 1, 7, 7, 1, 7, 7, 7, 7, 2, 7, 7, 2, 7, 0, 0, 7, 2, 7, 7, 2, 7, 7, 1,
    7, 2, 7, 7, 2, 7, 0, 1, 7, 2, 7, 7, 2, 3, 3, 3, 7, 3, 7, 7, 3, 3, 0, 0, 7,
    0, 7, 7, 0, 3, 3, 1, 7, 1, 7, 7, 1, 3, 0, 1, 7, 1, 7, 7, 1, 3, 3, 3, 7, 2,
    7, 7, 2, 3, 0, 0, 7, 2, 7, 7, 2, 3, 3, 1, 7, 2, 7, 7, 2, 3, 0, 1, 7, 2, 7,
    7, 2, 7, 7, 7, 7, 7, 7, 7, 4, 7, 0, 0, 7, 0, 7, 7, 4, 7, 7, 1, 7, 1, 7, 7,
    4, 7, 0, 1, 7, 1, 7, 7, 4, 7, 7, 7, 7, 2, 7, 7, 4, 7, 0, 0, 7, 2, 7, 7, 4,
    7, 7, 1, 7, 2, 7, 7, 4, 7, 0, 1, 7, 2, 7, 7, 4, 3, 3, 3, 7, 3, 7, 7, 4, 3,
    0, 0, 7, 0, 7, 7, 4, 3, 3, 1, 7, 1, 7, 7, 4, 3, 0, 1, 7, 1, 7, 7, 4, 3, 3,
    3, 7, 2, 7, 7, 4, 3, 0, 0, 7, 2, 7, 7, 4, 3, 3, 1, 7, 2, 7, 7, 4, 3, 0, 1,
    7, 2, 7, 7, 4, 5, 5, 5, 5, 5, 7, 7, 5, 5, 0, 0, 5, 0, 7, 7, 0, 5, 5, 1, 5,
    1, 7, 7, 1, 5, 0, 1, 5, 1, 7, 7, 1, 5, 5, 5, 5, 2, 7, 7, 2, 5, 0, 0, 5, 2,
    7, 7, 2, 5, 5, 1, 5, 2, 7, 7, 2, 5, 0, 1, 5, 2, 7, 7, 2, 3, 3, 3, 5, 3, 7,
    7, 3, 3, 0, 0, 5, 0, 7, 7, 0, 3, 3, 1, 5, 1, 7, 7, 1, 3, 0, 1, 5, 1, 7, 7,
    1, 3, 3, 3, 5, 2, 7, 7, 2, 3, 0, 0, 5, 2, 7, 7, 2, 3, 3, 1, 5, 2, 7, 7, 2,
    3, 0, 1, 5, 2, 7, 7, 2, 5, 5, 5, 5, 5, 7, 7, 4, 5, 0, 0, 5, 0, 7, 7, 4, 5,
    5, 1, 5, 1, 7, 7, 4, 5, 0, 1, 5, 1, 7, 7, 4, 5, 5, 5, 5, 2, 7, 7, 4, 5, 0,
    0, 5, 2, 7, 7, 4, 5, 5, 1, 5, 2, 7, 7, 4, 5, 0, 1, 5, 2, 7, 7, 4, 3, 3, 3,
    5, 3, 7, 7, 4, 3, 0, 0, 5, 0, 7, 7, 4, 3, 3, 1, 5, 1, 7, 7, 4, 3, 0, 1, 5,
    1, 7, 7, 4, 3, 3, 3, 5, 2, 7, 7, 4, 3, 0, 0, 5, 2, 7, 7, 4, 3, 3, 1, 5, 2,
    7, 7, 4, 3, 0, 1, 5, 2, 7, 7, 4, 6, 6, 6, 6, 6, 6, 7, 6, 6, 0, 0, 6, 0, 6,
    7, 0, 6, 6, 1, 6, 1, 6, 7, 1, 6, 0, 1, 6, 1, 6, 7, 1, 6, 6, 6, 6, 2, 6, 7,
    2, 6, 0, 0, 6, 2, 6, 7, 2, 6, 6, 1, 6, 2, 6, 7, 2, 6, 0, 1, 6, 2, 6, 7, 2,
    3, 3, 3, 6, 3, 6, 7, 3, 3, 0, 0, 6, 0, 6, 7, 0, 3, 3, 1, 6, 1, 6, 7, 1, 3,
    0, 1, 6, 1, 6, 7, 1, 3, 3, 3, 6, 2, 6, 7, 2, 3, 0, 0, 6, 2, 6, 7, 2, 3, 3,
    1, 6, 2, 6, 7, 2, 3, 0, 1, 6, 2, 6, 7, 2, 6, 6, 6, 6, 6, 6, 7, 4, 6, 0, 0,
    6, 0, 6, 7, 4, 6, 6, 1, 6, 1, 6, 7, 4, 6, 0, 1, 6, 1, 6, 7, 4, 6, 6, 6, 6,
    2, 6, 7, 4, 6, 0, 0, 6, 2, 6, 7, 4, 6, 6, 1, 6, 2, 6, 7, 4, 6, 0, 1, 6, 2,
    6, 7, 4, 3, 3, 3, 6, 3, 6, 7, 4, 3, 0, 0, 6, 0, 6, 7, 4, 3, 3, 1, 6, 1, 6,
    7, 4, 3, 0, 1, 6, 1, 6, 7, 4, 3, 3, 3, 6, 2, 6, 7, 4, 3, 0, 0, 6, 2, 6, 7,
    4, 3, 3, 1, 6, 2, 6, 7, 4, 3, 0, 1, 6, 2, 6, 7, 4, 5, 5, 5, 5, 5, 6, 7, 5,
    5, 0, 0, 5, 0, 6, 7, 0, 5, 5, 1, 5, 1, 6, 7, 1, 5, 0, 1, 5, 1, 6, 7, 1, 5,
    5, 5, 5, 2, 6, 7, 2, 5, 0, 0, 5, 2, 6, 7, 2, 5, 5, 1, 5, 2, 6, 7, 2, 5, 0,
    1, 5, 2, 6, 7, 2, 3, 3, 3, 5, 3, 6, 7, 3, 3, 0, 0, 5, 0, 6, 7, 0, 3, 3, 1,
    5, 1, 6, 7, 1, 3, 0, 1, 5, 1, 6, 7, 1, 3, 3, 3, 5, 2, 6, 7, 2, 3, 0, 0, 5,
    2, 6, 7, 2, 3, 3, 1, 5, 2, 6, 7, 2, 3, 0, 1, 5, 2, 6, 7, 2, 5, 5, 5, 5, 5,
    6, 7, 4, 5, 0, 0, 5, 0, 6, 7, 4, 5, 5, 1, 5, 1, 6, 7, 4, 5, 0, 1, 5, 1, 6,
    7, 4, 5, 5, 5, 5, 2, 6, 7, 4, 5, 0, 0, 5, 2, 6, 7, 4, 5, 5, 1, 5, 2, 6, 7,
    4, 5, 0, 1, 5, 2, 6, 7, 4, 3, 3, 3, 5, 3, 6, 7, 4, 3, 0, 0, 5, 0, 6, 7, 4,
    3, 3, 1, 5, 1, 6, 7, 4, 3, 0, 1, 5, 1, 6, 7, 4, 3, 3, 3, 5, 2, 6, 7, 4, 3,
    0, 0, 5, 2, 6, 7, 4, 3, 3, 1, 5, 2, 6, 7, 4, 3, 0, 1, 5, 2, 6, 7, 4};

/*------------------------------------------------------------------------*/

int Lx;
int Displace_vector[8];

#define E_PIX(pix) (*(pix + 1))

#define W_PIX(pix) (*(pix - 1))

#define N_PIX(pix) (*(pix + Lx))

#define S_PIX(pix) (*(pix - Lx))

#define SW_PIX(pix) (*(pix - Lx - 1))

#define NW_PIX(pix) (*(pix + Lx - 1))

#define NE_PIX(pix) (*(pix + Lx + 1))

#define SE_PIX(pix) (*(pix - Lx + 1))

#define NEIGHBOURS_CODE(pix)                                                   \
  (((SW_PIX(pix) != 0) << 0) | ((S_PIX(pix) != 0) << 1) |                      \
   ((SE_PIX(pix) != 0) << 2) | ((W_PIX(pix) != 0) << 3) |                      \
   ((E_PIX(pix) != 0) << 4) | ((NW_PIX(pix) != 0) << 5) |                      \
   ((N_PIX(pix) != 0) << 6) | ((NE_PIX(pix) != 0) << 7))

/*------------------------------------------------------------------------*/

#define FIRST_PRESEED(code) First_preseed_table[code]

/*------------------------------------------------------------------------*/

#define NEXT_POINT(code, preseed) Next_point_table[(code << 3) | preseed]

/*------------------------------------------------------------------------*/

#define UPDATE_POS(displ_code, x_pos, y_pos)                                   \
  switch (displ_code) {                                                        \
  case 0:                                                                      \
    x_pos--;                                                                   \
    y_pos--;                                                                   \
    break;                                                                     \
  case 1:                                                                      \
    y_pos--;                                                                   \
    break;                                                                     \
  case 2:                                                                      \
    x_pos++;                                                                   \
    y_pos--;                                                                   \
    break;                                                                     \
  case 3:                                                                      \
    x_pos--;                                                                   \
    break;                                                                     \
  case 4:                                                                      \
    x_pos++;                                                                   \
    break;                                                                     \
  case 5:                                                                      \
    x_pos--;                                                                   \
    y_pos++;                                                                   \
    break;                                                                     \
  case 6:                                                                      \
    y_pos++;                                                                   \
    break;                                                                     \
  case 7:                                                                      \
    x_pos++;                                                                   \
    y_pos++;                                                                   \
    break;                                                                     \
  default:                                                                     \
    assert(false);                                                             \
  }

/*------------------------------------------------------------------------*/

/*=============================================================================*/

/*---------------------------------------------------------------------------*/

static int fillByteRaster(const TRaster32P &rin, TRasterGR8P &rout) {
  bool ret = false;

  assert(rin->getLx() == rout->getLx() - 2 &&
         rin->getLy() == rout->getLy() - 2);

  memset(rout->getRawData(), 0, rout->getLx() * rout->getLy());

  for (int i = 0; i < rin->getLy(); i++) {
    TPixel32 *bufIn = (TPixel32 *)rin->getRawData() + i * rin->getWrap();
    UCHAR *bufOut = (UCHAR *)rout->getRawData() + (i + 1) * rout->getWrap() + 1;

    for (int j = 0; j < rin->getLx(); j++, bufIn++, bufOut++)
      if (bufIn->m != 0) {
        ret     = true;
        *bufOut = 1;
      }
  }
  return ret;
}

/*---------------------------------------------------------------------------*/

static void initialize_displace_vector(void) {
  Displace_vector[0] = -Lx - 1;
  Displace_vector[1] = -Lx;
  Displace_vector[2] = -Lx + 1;
  Displace_vector[3] = -1;
  Displace_vector[4] = +1;
  Displace_vector[5] = Lx - 1;
  Displace_vector[6] = Lx;
  Displace_vector[7] = Lx + 1;
}

/*------------------------------------------------------------------------*/

static int find_next_seed(const TRasterGR8P &r, bool first_seed, UCHAR *&seed,
                          int &x_pos, int &y_pos) {
  static int Curr_x = 0, Curr_y = 0;
  UCHAR *pix;

  if (first_seed) {
    Curr_x = 0;
    Curr_y = 0;
  }

  seed = 0;

  for (; Curr_y < r->getLy(); Curr_y++) {
    pix = (UCHAR *)r->getRawData() + Curr_y * r->getWrap() + Curr_x;
    for (; Curr_x < r->getLx(); Curr_x++, pix++)
      if (*pix == 1 &&
          (!E_PIX(pix) || !W_PIX(pix) || !N_PIX(pix) || !S_PIX(pix))) {
        seed  = pix;
        x_pos = Curr_x;
        y_pos = Curr_y;
        return true;
      }
    Curr_x = 0;
  }
  return false;
}

/*------------------------------------------------------------------------*/

#define COMPUTE_NUM_DEN(x_pos, y_pos, old_x_pos, old_y_pos)                    \
  {                                                                            \
    aux = old_x_pos * y_pos - x_pos * old_y_pos;                               \
    den += aux;                                                                \
    x_num += (x_pos + old_x_pos) * aux;                                        \
    y_num += (y_pos + old_y_pos) * aux;                                        \
  }

/*------------------------------------------------------------------------*/

static void doComputeCentroid(const TRasterGR8P &r, TPoint &cp) {
  int preseed, displ, prewalker, code;
  UCHAR *seed, *walker;
  int x_num = 0, y_num = 0, den = 0;
  int x_pos, y_pos, old_x_pos, old_y_pos;
  int aux, old_displ = -1;
  bool first_seed;

  Lx                 = r->getLx();
  Displace_vector[0] = -Lx - 1;
  Displace_vector[1] = -Lx;
  Displace_vector[2] = -Lx + 1;
  Displace_vector[3] = -1;
  Displace_vector[4] = +1;
  Displace_vector[5] = Lx - 1;
  Displace_vector[6] = Lx;
  Displace_vector[7] = Lx + 1;

  first_seed = true;

  while (find_next_seed(r, first_seed, seed, x_pos, y_pos)) {
    first_seed = false;

    *seed |= 0x2;

    code    = NEIGHBOURS_CODE(seed);
    preseed = FIRST_PRESEED(code);

    if (preseed == 8) continue;

    displ = NEXT_POINT(code, preseed);

    walker = seed + Displace_vector[displ];

    old_x_pos = x_pos;
    old_y_pos = y_pos;

    UPDATE_POS(displ, x_pos, y_pos)

    COMPUTE_NUM_DEN(x_pos, y_pos, old_x_pos, old_y_pos)

    prewalker = displ ^ 0x7;

    while ((walker != seed) || (preseed != prewalker)) {
      *walker |= 0x2;

      displ = NEXT_POINT(NEIGHBOURS_CODE(walker), prewalker);

      walker += Displace_vector[displ];
      old_x_pos = x_pos;
      old_y_pos = y_pos;
      UPDATE_POS(displ, x_pos, y_pos)
      COMPUTE_NUM_DEN(x_pos, y_pos, old_x_pos, old_y_pos)
      prewalker = displ ^ 0x7;
    }
  }

  if (den)
    cp = TPoint(tround(x_num / (3.0 * den)), tround(y_num / (3.0 * den)));
}

}  // namespace

TPoint computeCentroid(const TRaster32P &r) {
  TPoint ret(1, 1);

  TRasterGR8P raux(r->getLx() + 2, r->getLy() + 2);

  if (fillByteRaster(r, raux)) doComputeCentroid(raux, ret);

  ret.x--;
  ret.y--; /* per il bordo aggiunto */
  return ret;
}
